链表中的节点每k个一组翻转

// 递归做法
// 含义：返回以head开头的链表经k组反转后的首节点指针
function reverseKGroup(head, k){
    let tail = head;
    for(let i = 0; i<k; i++){
        if(!tail){
            return head;
        }
        tail = tail.next;
    }
    // 区间反转
    let l = null;
    let r = head;
    for(let i = 0; i<k; i++){
        const temp = r.next;
        r.next = l;
        l = r;
        r = temp;
    }
    // 递归调用
    head.next = reverseKGroup(r,k);
    return l;
}

//常规做法
function reverseKGroup( head ,  k ) {
    if(!head || !head.next || k === 1){
        return head;
    }

    let left = head;
    let right;
    const dummy = new ListNode(-1);
    let tail = dummy;
    tail.next = head;
    while(left){
        // 确定反转区间【left，right】
        right = left;
        for(let i = 1; i< k; i++){
            right = right.next;
            if(!right){
                right = null;
                break;
            }
        }
        // 链表不足k个节点
        if(!right){
            tail.next = left;
            break;
        }

        // 反转k个节点[left,right] 算法
        let l = null;
        let r = left;
        for(let i = 0; i<k; i++){
            const temp = r.next;
            r.next = l;
            l = r;
            r = temp;
        }

        // 将本组与上一组连接
        tail.next = l;
        tail = left;
        left = r;
    }
    head = dummy.next;
    return head;
}

// 浅用一下递归
function reverseKGroup(head, k) {
  // 定义一个用于翻转指定开始节点和长度区间内节点的函数
  function reversePart(startNode, step, flag) {
    if (startNode == null) return null;
    let curr = startNode.next;
    let prev = startNode;
    for (let i = 0; i < step; i++) {
      // 这种情况用于解决当k值大于剩余节点的个数时，将翻转的节点复原
      if (curr == null) {
        // 这里传flag为true表示用来恢复翻转的节点
        // 因为复原后的curr不为null
        // 所以不能通过curr是否为null来判断是否将satrtNode的next置null
        return reversePart(prev, i, true);
      }
      let temp = prev;
      prev = curr;
      curr = curr.next;
      prev.next = temp;
    }
    // curr != null用于判断是否为结尾
    // !flag 用于判断是否为复原之前的翻转操作
    startNode.next =
      curr != null && !flag ? reversePart(curr, step, false) : null;
    return prev;
  }
  return reversePart(head, k - 1, false);
}

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @param k int整型
 * @return ListNode类
 */
function reverseKGroup(head, k) {
    // write code here
    let t = head
    let count = 0;
    while (t != null) {
        count++;
        t = t.next;
    }
    if (count < k) {
        return head;
    }
    let number = count / k;
    let cur = head;
    let pre = null;
    let res = head;
    for (let j = 1; j <= number; j++) {
        let xx = cur
        for (let i = 1; i <= k; i++) {
            let temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        if (j === 1) {
            head = pre;
        } else {
            res.next = pre;
        }
        res = xx;
    }
    res.next = cur;
    return head;
}

module.exports = {
    reverseKGroup: reverseKGroup
};

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup( head ,  k ) {
    // write code here
    let headNode = head
    //当k超过节点数时，直接返回
    for(let i=0;i<k;i++){
        if(headNode == null){
            return head
        }
        headNode = headNode.next
    }
    
    //对k个节点进行逆转（进行k-1此指向转换）
    let cur = head.next
    let pre = head
    for(let i=1;i<k;i++){
        let tmp = cur.next
        cur.next = pre
        pre = cur 
        cur = tmp       
    }
    //递归对下一组k个进行逆转，且每次都是把head指向下一组
    head.next = reverseKGroup(cur,k)
    //返回每一组逆序后实际的头节点（就是当前pre指向的，即每组第k个元素）
    return pre
}
module.exports = {
    reverseKGroup : reverseKGroup
};